package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-27 18:06
 */
public class QLint563 {
    //前i个背包能拼出w的方案数
    public int backPackV(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[][] dp = new int[len + 1][target + 1];
        //当你不知道第一个怎么取值的时候，带入到后面的递推关系中
        dp[0][0] = 1;

        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] += dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[len][target];
    }

    public int backPackV2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[target + 1];
        //当你不知道第一个怎么取值的时候，带入到后面的递推关系中
        dp[0] = 1;

        for (int i = 1; i <= len; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i - 1]) {
                    dp[j] += dp[j - nums[i - 1]];
                }
            }
        }

        return dp[target];
    }
}
